package pri.hillchen.algorithm.array;

/**
 * 查询两排序数组的中位数 leetcode#4
 * Created by hillchen on 2017/9/25 0025.
 */
public class MedianOfTowStotedArray {
    class KMinRet{
        private Integer aLastIndex;
        private Integer bLastIndex;
        public Integer getaLastIndex() {
            return aLastIndex;
        }

        public void setaLastIndex(Integer aLastIndex) {
            this.aLastIndex = aLastIndex;
        }

        public Integer getbLastIndex() {
            return bLastIndex;
        }

        public void setbLastIndex(Integer bLastIndex) {
            this.bLastIndex = bLastIndex;
        }
    }

    class NoFindException extends RuntimeException{
        public NoFindException() {
        }

        public NoFindException(String message) {
            super(message);
        }

        public NoFindException(String message, Throwable cause) {
            super(message, cause);
        }

        public NoFindException(Throwable cause) {
            super(cause);
        }

    }
    /**
     *
     * @param arrayA
     * @param aStartIndex
     * @param aLength
     * @param arrayB
     * @param bStartIndex
     * @param bLength
     * @param k
     * @param kMinRet
     * @return
     */
    public int findKMin(int[] arrayA,int aStartIndex,int aLength,int[] arrayB,int bStartIndex, int bLength, int k,KMinRet kMinRet ){
        kMinRet.aLastIndex = aStartIndex + aLength - 1;
        kMinRet.bLastIndex = bStartIndex + bLength - 1;
        int kthValue;
        if(aLength + bLength < k){
            throw new NoFindException("没有找到指定k大小的值，两数组可取长度之和小于k值！");
        }else if(aLength + bLength == k){
            kthValue = arrayA[kMinRet.aLastIndex] > arrayB[kMinRet.bLastIndex] ? arrayA[kMinRet.aLastIndex] : arrayB[kMinRet.bLastIndex];
        }else{
            if(aLength == 0){
                kMinRet.bLastIndex = bStartIndex + k -1;
                kthValue = arrayB[kMinRet.bLastIndex];
            }else if(bLength == 0 ){
                kMinRet.aLastIndex = aStartIndex + k -1;
                kthValue = arrayA[kMinRet.aLastIndex];
            }else{
                if(k == 1){
                    kMinRet.aLastIndex = aStartIndex;
                    kMinRet.bLastIndex = bStartIndex;
                    kthValue  = arrayA[kMinRet.aLastIndex] > arrayB[kMinRet.bLastIndex] ? arrayB[kMinRet.bLastIndex] : arrayA[kMinRet.aLastIndex] ;
                }else{
                    int kMind = k/2;
                    if(kMind < aLength){
                        kMinRet.aLastIndex = aStartIndex + kMind -1;
                    }
                    if(kMind < bLength){
                        kMinRet.bLastIndex = bStartIndex + kMind -1;
                    }
                    int filterCount;
                    if(arrayA[kMinRet.aLastIndex] <= arrayB[kMinRet.bLastIndex]){
                        filterCount =   kMinRet.aLastIndex + 1 - aStartIndex;
                        kthValue = findKMin(arrayA,kMinRet.aLastIndex + 1, aLength - filterCount,arrayB,bStartIndex,bLength,k - filterCount,kMinRet);
                    }else{
                        filterCount = kMinRet.bLastIndex + 1 - bStartIndex;
                        kthValue = findKMin(arrayA,aStartIndex, aLength,arrayB,kMinRet.bLastIndex + 1 ,bLength - filterCount,k - filterCount,kMinRet);
                    }
                }
            }
        }
        return kthValue;
    }

    public double findMedian(int[] arrayA,int aStartIndex,int aLength,int[] arrayB,int bStartIndex, int bLength){
        int allLength = aLength + bLength;
        int medianK = allLength / 2;
        KMinRet kMinRet = new KMinRet();
        int kthValue = findKMin( arrayA,aStartIndex,aLength, arrayB, bStartIndex,bLength, medianK,kMinRet );
        if(allLength % 2 == 0 ){
            return kthValue;
        }else{
            int medianNext ;
            if(kMinRet.getaLastIndex() == null ){
                medianNext = arrayB[kMinRet.getbLastIndex() + 1];
            }else if(kMinRet.getbLastIndex() == null){
                medianNext = arrayA[kMinRet.getaLastIndex() + 1];
            }else{
                medianNext = arrayA[kMinRet.getaLastIndex() + 1] < arrayB[kMinRet.getbLastIndex() + 1] ? arrayA[kMinRet.getaLastIndex() + 1] : arrayB[kMinRet.getbLastIndex() + 1];
            }
            double sumMedian = kthValue + medianNext;
            return sumMedian / 2.0;
        }
    }
    public static void main(String[] args){
        int[] arrayA = {1,3,4,5,6,7,8,10,15,18};
        int[] arrayB = {2,9,11,12,13,14,16,17};

        double  dedian = new MedianOfTowStotedArray().findMedian(arrayA,0,10,arrayB,0,5);
        System.out.println(dedian == 7.5 );
    }
}
